#include "queue.h"

// 初始化队列
// 参数 capacity 为队列最大能容纳的元素个数，node_size 为每个节点数据的字节数
// 成功返回队列指针，失败返回 NULL
Queue_t *queue_init(int capacity, size_t node_size)
{
    Queue_t *q = (Queue_t *)malloc(sizeof(Queue_t));
    if (!q)
        return NULL;

    q->data = malloc(capacity * node_size);
    if (!q->data) {
        free(q);
        return NULL;
    }
    q->head = 0;
    q->tail = 0;
    q->count = 0;
    q->capacity = capacity;
    q->node_size = node_size;
    return q;
}

// 入队操作：将元素插入到队列尾部
// 如果队列已满，则丢弃最老的节点（队头元素），再插入新元素
// 参数 element 指向要插入的数据
// 成功返回 0
int queue_enqueue(Queue_t *q, const void *element)
{
    // 如果队列已满，则将队头指针后移（丢弃最老的元素）
    if (q->count == q->capacity) {
        q->head = (q->head + 1) % q->capacity;
    }
    else {
        // 未满时增加元素个数
        q->count++;
    }
    // 将数据复制到队尾对应的位置
    void *target = (char *)q->data + (q->tail * q->node_size);
    memcpy(target, element, q->node_size);
    // 更新队尾索引（循环）
    q->tail = (q->tail + 1) % q->capacity;
    return 0;
}

// 出队操作：从队列头部弹出元素
// 参数 out_element 指向的缓冲区用于存放弹出的数据
// 成功返回 0，若队列为空则返回 -1
int queue_dequeue(Queue_t *q, void *out_element)
{
    if (q->count == 0) {
        // 队列为空
        return -1;
    }
    void *source = (char *)q->data + (q->head * q->node_size);
    if (out_element) {
        memcpy(out_element, source, q->node_size);
    }
    // 更新队头索引（循环）
    q->head = (q->head + 1) % q->capacity;
    q->count--;
    return 0;
}

// 从队列中删除指定逻辑位置（相对于队头，0 为队头）的节点
void queue_remove_at(Queue_t *queue, int index)
{
    // 1. 检查参数有效性
    if (!queue || index < 0 || index >= queue->count)
        return;

    // 2. 根据逻辑索引计算待删除节点在内部数组中的实际索引
    int pos = (queue->head + index) % queue->capacity;

    /*
     * 3. 为了减少内存移动的操作：
     *    如果待删除节点离队头较近，则将 [head, pos-1] 区间的元素向后移一位，
     *    否则，如果待删除节点离队尾较近，则将 [pos+1, tail-1] 区间的元素向前移一位。
     */
    if (index < (queue->count - index - 1)) {
        // 待删除节点更接近队头：将区间 [head, pos-1] 元素右移
        while (pos != queue->head) {
            int prev = (pos - 1 + queue->capacity) % queue->capacity;
            memcpy((char *)queue->data + pos * queue->node_size,
                   (char *)queue->data + prev * queue->node_size,
                   queue->node_size);
            pos = prev;
        }
        // 更新队头指针（队头向后移动一位）
        queue->head = (queue->head + 1) % queue->capacity;
    }
    else {
        // 待删除节点更接近队尾：将区间 [pos+1, tail-1] 元素左移
        while (pos != (queue->tail - 1 + queue->capacity) % queue->capacity) {
            int next = (pos + 1) % queue->capacity;
            memcpy((char *)queue->data + pos * queue->node_size,
                   (char *)queue->data + next * queue->node_size,
                   queue->node_size);
            pos = next;
        }
        // 更新队尾指针（队尾向前移动一位）
        queue->tail = (queue->tail - 1 + queue->capacity) % queue->capacity;
    }

    // 4. 更新队列中元素数量
    queue->count--;
}

// 释放队列占用的内存
void queue_destroy(Queue_t *q)
{
    if (q) {
        free(q->data);
        free(q);
    }
}

/*
 * 获取队列中指定位置的节点数据指针
 * 参数：
 *   q            - 指向队列的指针
 *   head_or_tail - 如果非零，从队头开始计数；如果为零，从队尾开始计数
 *   index        - 指定序号（0表示第一个节点或最后一个节点）
 * 返回：
 *   该节点数据的指针；如果队列为空或 index 越界则返回 NULL
 */
void *queue_get_node(Queue_t *q, int head_or_tail, int index)
{
    if (!q || index < 0 || index >= q->count) {
        return NULL;
    }
    int pos = 0;
    if (head_or_tail == from_head) {
        // 从队头计数，队头位置为 q->head
        pos = (q->head + index) % q->capacity;
    }
    else if (head_or_tail == from_tail) {
        // 从队尾计数：队尾指针 q->tail 指向下一个插入位置，因此最后一个有效元素在 (q->tail - 1)
        pos = (q->tail - 1 - index + q->capacity) % q->capacity;
    }
    return (char *)q->data + (pos * q->node_size);
}

int get_queue_count(Queue_t *q)
{
    return q->count;
}